package com.whitedust.top20;

/*
 * @author A
 * @since 2025/11/3 12:55
 */

import java.util.LinkedList;
import java.util.Queue;

public class Top12 {
    //深搜和广搜的模板题目
    //深搜递归，广搜采用队列
    private final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    private void dfs(boolean[][] visited, char[][] grid, int x, int y) {
        if (visited[x][y] || grid[x][y] == '0') return;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) continue;
            dfs(visited, grid, nextX, nextY);
        }
    }

    private void bfs(boolean[][] visited, char[][] grid, int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            int curX = queue.peek()[0];
            int curY = queue.poll()[1];
            for (int i = 0; i < 4; i++) {
                int nextX = curX + dir[i][0];
                int nextY = curY + dir[i][1];
                if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length)
                    continue;
                if (!visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                    visited[nextX][nextY] = true;
                    queue.add(new int[]{nextX, nextY});
                }
            }
        }
    }

    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
//                    bfs(visited, grid, i, j);
                    dfs(visited, grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }
}
